This application relates generally to integrated circuit (“IC”) and printed circuit board (“PCB”) design, and more particularly to automated or semi-automated methods of determining interconnections or paths between components or subcomponents that need to communicate with each other. The description will be in terms of PCB design, but embodiments of the present invention can be used for IC package design, and possibly for IC routing or redistribution layer (RDL) routing.
Finding a geometric solution for a design is commonly referred to as “routing” the design. If the routing is done automatically, the process is called “autorouting” and the mechanism or algorithm doing the autorouting is called an “autorouter.” When this process is done interactively by a human operator, often called a “PCB designer,” the process is called “manual routing.”
The basic job of any autorouter is to connect “pads” according to a user-specified “netlist” and user-specified “constraints.” The term “pad” refers to a location on a design to which printed wires can be connected (depending on the vendor and the underlying technology, pads might have many different names, such as terminals, pins, bumps, balls, or I/O pads). The “netlist” describes which pads must be connected together by “wires” and (optionally) in what order they must be connected. The term “connection” will be used to mean a set of one or more source pads and a set of one or more target pads for which one or more connecting paths are to be found. The path(s) are ultimately implemented as one or more signal traces on a PCB or semiconductor package, for example.
The term “constraint” refers to a rule that must be met by the paths implementing the netlist connections. Some constraints are physical, such as “Keep the paths of net A at least 5 mil away from the paths of net B.” Some constraints are electrical, such as “The propagation delay between pads P1 and P2 must be less than x nanoseconds.” Still other constraints are defined in terms of match or relative units. For example, “Path A and path B must have the same propagation delay (to within a tolerance of ±x nanoseconds)” or “The total paths length between pads P1 and P2 must be at least x % longer than the paths length between pads P2 and P3.” At least some constraints can be addressed by applying “elongation” to routed paths. The term “elongation” refers to changing the length(s) or delay(s) of the path(s) of one or more connections that are subject to the constraint.
Autorouting is known to be “intractable” (also called EXPTIME-Complete). In other words, it is one of a class of computationally hard problems for which there is no polynomial-time bounded solution. In simpler terms, the term “intractable” refers to the fact that finding the absolute best solution for a “reasonably” large data set is not possible in a “reasonable” amount of time. Although it is theoretically possible to consider every possible geometric solution and then select the best solution, doing so might take hundreds of years. Thus, the autorouting problem has always been about finding a “reasonable” solution in a “reasonable” amount of time.
Most (if not all) modern commercial autorouters use a routing engine algorithm called a Single Connection Router (“SCR”) to find one path for one connection, where a connection consists of two sets of pads from the same signal that need to be connected to meet the design requirements. The first set of pads is generally referred to as the “source”; the other set is referred to as the “target.” Note that it is very common that each set has only one pad. In this case, the autorouter must connect one source pad to one target pad. The SCR is used repeatedly to connect one set of source pads to one set of target pads until all connections have paths and the design meets all design constraints, including electrical constraints (such as match).
An increasing percentage of modern designs are both geometrically dense and have many electrical constraints. For such designs, there may not enough real estate remaining for the autorouter or for a manual designer to add the necessary elongation to meet all of the constraints.